//一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [4,1,4,6]
//输出：[1,6] 或 [6,1]
// 
//
// 示例 2： 
//
// 输入：nums = [1,2,10,4,1,4,3,3]
//输出：[2,10] 或 [10,2] 
//
// 
//
// 限制： 
//
// 
// 2 <= nums.length <= 10000 
// 
//
// 
// Related Topics 位运算 数组 
// 👍 626 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Code56 {

    public static void main(String[] args) {

        Solution56 solution = new Solution56();

//        System.out.println(solution.movingCount(6, 1, 0));

//        System.out.println(solution.lengthOfLongestSubstring("abcdabcdd"));
//        int[] ints = {3,4,3,3};
//        System.out.println(solution.singleNumber(ints));
//        int[] ints1 = solution.singleNumbers(ints);
//        for (int i: ints1){
//            System.out.printf("%d\t",i);
//        }
    }
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution56 {

    public static int count = 0;

    public static void main(String[] args) {

        int[][] map = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(map));
    }

    public static int minPathSum(int[][] grid) {
        boolean[][] vistied = new boolean[grid.length][grid[0].length];
        return path(grid, 0, 0, vistied);
    }

    public static int path(int[][] map, int i, int j, boolean[][] vistied) {
        if (i < 0 || i >= map.length || j < 0 || j >= map[0].length) {
            return 0;
        }
        if(i == (map.length - 1) && j == (map[0].length - 1)){
            return 0;
        }
        if(vistied[i][j]){
            return 0;
        }
        System.out.printf("map[%d][%d]",i,j);
        vistied[i][j] = true;
        return path(map, i, j + 1, vistied) +
                // 向下
                path(map, i + 1, j, vistied) + map[i][j];
    }


    public int movingCount(int[][] map, int i, int j) {
        return 0;
    }


    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        int i = -1;
        int last = 0;
        for (int j = 0; j < chars.length; j++) {
            if (map.containsKey(chars[j])) {
                i = Math.max(i, map.get(chars[j]));
            }
            map.put(chars[j], j);
            last = Math.max(last, j - i);
        }
        return last;
    }

    public int sumNums(int n) {
        if (n == 0) {
            return 0;
        }
        int result = 0;
        if (n == 1) {
            return 1;
        }
        return sumNums(n - 1) + n;
    }


    public int singleNumber(int[] nums) {
        int m = 0;
        for (int num : nums) {
            m ^= num;
        }
        return m;
    }

    public int[] singleNumbers(int[] nums) {
        int n = 0;
        for (int i : nums) {
            n ^= i;
        }
        int m = 1;
        while ((n & m) == 0) {
            m <<= 1;
        }
        int x = 0, y = 0;
        for (int num : nums) {
            if ((num & m) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }

    public int[] singleNumbers1(int[] nums) {
        if (nums.length == 0) {
            return new int[]{};
        }
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        int[] ints = new int[2];
        for (int i : nums) {
            if (map.containsKey(i)) {
                map.remove(i);
            } else {
                map.put(i, i);
            }
        }
        int count = 0;
        for (Integer m : map.values()) {
            ints[count] = m;
            count++;
        }
        return ints;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
